package algorithm.swordoff;

import algorithm.leetcode.ListNode;

/**
 * 两个链表的第一个公共节点
 *
 * 要求时间复杂度O(N),空间复杂度O(1)
 * 思路: 先获取两个链表的长度,然后对其尾部,最后两个同步逐个遍历+判断
 */

public class SQ52 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int a = 0, b = 0;
        ListNode tempA = headA, tempB = headB;
        while (tempA != null || tempB != null) {
            if (tempA != null) {
                a++;
                tempA = tempA.next;
            }
            if (tempB != null) {
                b++;
                tempB = tempB.next;
            }
        }
        tempA = headA;
        tempB = headB;
        while (a > b) {
            tempA = tempA.next;
            a--;
        }
        while (b > a) {
            tempB = tempB.next;
            b--;
        }
        while (tempA != tempB && tempA != null) {
            tempA = tempA.next;
            tempB = tempB.next;
        }

        return tempA;
    }

    public static void main(String[] args) {
        SQ52 sq52 = new SQ52();
        ListNode a = new ListNode(2);
        ListNode b = new ListNode(6);
        ListNode c = new ListNode(4);
        ListNode d = new ListNode(1);
        ListNode e = new ListNode(5);
//        ListNode f = new ListNode(6);
        a.next = b;
        b.next = c;
        // c.next = d;
        d.next = e;
        System.out.println(sq52.getIntersectionNode(a, d));
    }
}
